Programmable logic devices (“PLDs”) (also sometimes referred to as complex PLDs (“CPLDs”), programmable array logic (“PALs”), programmable logic arrays (“PLAs”), field PLAs (“FPLAs”), erasable PLDs (“EPLDs”), electrically erasable PLDs (“EEPLDs”), logic cell arrays (“LCAs”), field programmable gate arrays (“FPGAs”), or by other names), are well-known integrated circuits that provide the advantages of fixed integrated circuits with the flexibility of custom integrated circuits. Such devices typically provide an “off the shelf” device having at least a portion that can be programmed to meet a user's specific needs. Application specific integrated circuits (“ASICs”) have traditionally been fixed integrated circuits. However, it is possible to provide an ASIC that has a portion or portions that are programmable. Thus, it is possible for an integrated circuit device to have qualities of both an ASIC and a PLD. The term PLD as used herein will be considered broad enough to include such devices.
PLDs have configuration elements that may be programmed or reprogrammed. Configuration elements may be realized as random access memory (“RAM”) bits, flip-flops, electronically erasable programmable read-only memory (“EEPROM”) cells, or other memory elements. Placing new data into the configuration elements programs or reprograms the PLD's logic functions and associated routing pathways. Configuration elements that are field programmable are often implemented as RAM cells (sometimes referred to a “configuration RAM” (“CRAM”)). However, many types of configurable elements may be used including static or dynamic RAM (“SRAM” or “DRAM”), electrically erasable read-only memory (“EEROM”), flash, fuse, and anti-fuse programmable connections. The programming of configuration elements could also be implemented through mask programming during fabrication of the device. While mask programming may have disadvantages relative to some of the field programmable options already listed, it may be useful in certain high volume applications. For purposes herein, the generic term “configuration element” will be used to refer to any programmable element that may be configured to determine functions implemented by other PLD elements.
PLDs typically include blocks of logic elements, sometimes referred to as logic array blocks (“LABs”; also referred to by other names, e.g., “configurable logic blocks” (“CLBs”)). Typically, the basic functional block of a LAB is a logic element (“LE”) that is capable of performing logic functions on a number of input variables. LEs, which are sometimes referred to by other names, e.g., “logic cells”, may include a look-up table (LUT) or product term, carry-out chain, register, and other elements. PLDs typically combine together large numbers of such LEs through an array of programmable interconnects to facilitate implementation of complex logic functions. LABs (comprising multiple LEs) may be connected to horizontal and vertical conductors that may or may not extend the length of the PLD.
A LE is sometimes used to perform a multiplexing function on its data input variables. In many cases, the LUT within a LE performs the multiplexing function. The number of data input variables on which multiplexing may be performed is determined by the number of input terminals of the LUT. The sum of the number of data input variables to be multiplexed and the number of select signals necessary for selecting from among the data input variables must be less than or equal to the number of input terminals of the LUT. There are a number of known ways of increasing the number of data input variables that are multiplexed. In one method, LEs are coupled in series. In other words, the outputs of a first stage of LEs are fed into a second stage of LEs. More specifically, the outputs of LUTs in the first stage of LEs are fed into the LUTs in the second stage of LEs, where both the first stage LUTs and second stage LUTs perform a multiplexing function on their respective data input variables. In another method, the outputs of multiple LEs (or LUTs therein) which perform a multiplexing function on their data input variables are fed into hardwired multiplexer(s).
Another function performed by LEs is barrel shifting. Those skilled in the art know that barrel shifting is the process of shifting data input signals by a number of bits depending on select signals that determine the extent of the shift. Those skilled in the art also know that there are generally two types of barrel shifting. In one type of barrel shifting, N data bits (where N is an integer) are shifted down by m bits and the top m bits (where m is an integer less than or equal to N) are all replaced by binary low signals, i.e., zeros, or by binary high signals, i.e., ones. For example, data input signals on input terminals 1 to 16, may be shifted by 5 bits such that input data “abcdefghijklmnop” is barrel shifted and “00000abcdefghijk” is output. In another type of barrel shifting (sometimes referred to as rotating barrel shifting), the shifted out data is placed at the top of the data stream. For example in a rotating barrel shifting process, a 5 bit shift of “abcdefghijklmnop” results in “lmnopabcdefghijk”.
Yet another function performed by LEs is crossbarring of input data. Crossbarring is a more general case of barrel shifting. In barrel shifting, both the input data and the select signals are the same. On the other hand, in the case of crossbarring, the input data are the same, but the select signals are different. In other words, the same input data are selected using different sets of select signals as a result of which different subsets of input data are selected.
Some known methods for implementing one or more of multiplexers, barrel shifters, and crossbars suffer from inefficiencies in the number of LEs required and/or the number of levels of LEs required to perform the desired function. The number of LEs required to perform the function is at times referred to as the LE density. The number of levels of LEs required to perform the function is at times referred to as the depth of the logic circuit. The depth of the logic circuit affects the speed with which the logic circuit performs its intended functions. Generally, all else being equal, logic circuits with lower depth perform functions faster than those with higher depth. As used herein, improved logic circuit efficiency refers to improved density (i.e., lower density) and/or improved depth (i.e., lower depth).
The present invention is directed to improving the efficiency of logic circuits for implementing one or more of multiplexers, barrel shifters, and crossbars, and to improve the consistency of delay through the multiplexing structure of the logic circuit with minimum impact on the routing algorithms of the PLD of which the logic circuit is a part.